\graphicspath{{Podkopaev/images/}}%путь к рисункам

\lstdefinelanguage{haskell}{
keywords={import, qualified, as, data, type, case, of, where, otherwise, in, let, deriving},
sensitive=true,
basicstyle=\small,
commentstyle=\scriptsize\rmfamily,
keywordstyle=\ttfamily\underbar,
identifierstyle=\ttfamily,
basewidth={0.5em,0.5em},
columns=fixed,
fontadjust=true,
literate={->}{{$\to$}}1
}

\lstset{
basicstyle=\small,
identifierstyle=\ttfamily,
keywordstyle=\bfseries,
commentstyle=\scriptsize\rmfamily,
basewidth={0.5em,0.5em},
fontadjust=true,
escapechar=~
%language=haskell
}

\title{Полиномиальной сложности\\
оптимальные принтер-комбинаторы\\ 
с выбором}
%
\titlerunning{Оптимальные принтер-комбинаторы}
\author{Подкопаев Антон Викторович}
%
\authorrunning{А.В.Подкопаев} % abbreviated author list (for running head)
%
%%%% list of authors for the TOC (use if author list has to be modified)
\tocauthor{А.В.Подкопаев}
%
\institute{Санкт-Петербургский государственный университет\\
\email{podkoav239@gmail.com}}

\maketitle              % typeset the title of the contribution

\begin{abstract}
В работе описана задача претти-принтинга. Приведено описание оригинальных
принтер-комбинаторов, обладающих улучшенными по сравнению с существующими 
работами алгоритмическими свойствами.
Также описано применение данных принтер-комбинаторов для задачи печати программ на
языке Java по образцу.
\end{abstract}

\section*{Введение}

В жизненном цикле программного обеспечения важную роль занимает этап
поддержки~\cite{maintance}. На этом этапе особую роль приобретает
понимание программного текста поддерживаемой системы, что часто бывает
достаточно сложной задачей. В данном контексте существенным достоинством
программного текста становится его аккуратное оформление.
В качестве примера рассмотрим два описания одной и той же функции на языке C
(см. рис.~\ref{fig:wikiExUnfor} и \ref{fig:wikiExBSD}).

\begin{figure}[h!]
	\centering
	\lstinputlisting[language=C]{Podkopaev/codes/wikiExUnfor.c}
	\caption{Неформатированный код}
	\label{fig:wikiExUnfor}
\end{figure}

\begin{figure}[h!]
	\centering
	\lstinputlisting[language=C]{Podkopaev/codes/wikiExBSD.c}
  \caption{Форматированный код (BSD)}
	\label{fig:wikiExBSD}
\end{figure}

C точки зрения компилятора
эти описания функции \lstinline[language = Java]{foo}
семантически и синтаксически эквиваленты.
Однако, вариант, приведенный на
рис.~\ref{fig:wikiExUnfor}, гораздо труднее для
понимания, а следовательно и изменения.
Как мы видим из этого примера, для возможности дальнейшей поддержки
программные тексты должны явным образом
отражать структуру программы, что для широкого класса языков
программирования означает явное представление структуры синтаксического
дерева программы.

Кроме того, распространенной практикой~\cite{codingStandarts},
доказавшей свою состоятельность, является использование
общепроектного стандарта кодирования.
\emph{Стандарт кодирования} (СК, coding convention) ---
это набор соглашений, которые используются
при написании программного кода. В него входят: способы выбора имен переменных
и других идентификаторов, стили отступов при оформлении логических блоков,
способы расстановки ограничителей логических блоков (скобок),
формат комментариев. СК также призван упростить анализ и изменение
программы, поэтому его важно соблюдать, что вводит
дополнительные, относительно требований компилятора,
ограничения на исходные тексты. СК разных проектов, даже
реализуемых на одном и том же языке программирования, могут существенно
различаться.
Так, код на рис.~\ref{fig:wikiExBSD} соответствует СК
BSD\footnote{\cd{http://www.freebsd.org/cgi/man.cgi?query=style\&sektion=9}},
а на рис.~\ref{fig:wikiExGNU} ---
GNU\footnote{\cd{http://www.gnu.org/prep/standards/standards.pdf}}.

\begin{figure}[h!]
	\centering
	\lstinputlisting[language=C]{Podkopaev/codes/wikiExGNU.c}
  \caption{Форматированный код (GNU)}
	\label{fig:wikiExGNU}
\end{figure}

Кроме ситуаций, когда СК в проекте поддерживается при написании
программного кода вручную, существует другой важный пример использования СК ---
в языковых процессорах. \emph{Языковой процессор} (ЯП) ---
это программное средство, принимающее на вход программу в виде текста
на некотором языке (программирования, разметки и т. д.) и решающее
определенную задачу над этой программой. К языковым процессорам можно
отнести компиляторы, суперкомпиляторы, интерпретаторы,
средства статического анализа кода, декомпиляторы, средства рефакторинга,
средства реинжиниринга, интегрированные среды разработки (IDE) и др.

Первым этапом работы ЯП является \emph{синтаксический анализ}, то есть
сопоставление входного текста (линейной последовательности лексем) с формальной
грамматикой языка. В результате работы синтаксического анализатора ЯП получает
древовидное представление программы, над которым потом происходит основная работа.

Дальше перед большим классом ЯП возникает задача показать пользователю
промежуточный или конечный результат обработки кода.
Следовательно, необходимо вернуться к текстовому представлению программы,
то есть провести процедуру, обратную синтаксическому анализу. Такая задача
называется \emph{pretty printing}, а соответствующий инструмент ---
\emph{pretty printer}. Далее этот инструмент мы будем называть
\emph{принтером}.

Сформулируем требования, которые накладываются на принтер.
Как уже понятно, принтер должен
продуцировать текст, который удовлетворяет проектному СК.
Классически считается, что изменение идентификаторов, как и любое другое
преобразование абстрактного синтаксического дерева программы, не входит в
задачи принтера, поэтому из всех ограничений СК принтеру остается 
соблюдать только правила форматирования логических структур и отступов.
Это требование, при правильном СК, решает проблему наглядности кода в том смысле,
что в полученном тексте явным образом отражается логическая структура программы.
Кроме того, в большинстве случаев СК оставляет некоторую свободу в представлении
синтаксических конструкций, а значит, может быть введено дополнительное
ограничение --- ограничение на ширину вывода принтера, а среди 
представлений, подпадающих под ограничения, может быть
найдено \emph{оптимальное}. Часто в данном случае под
оптимальным представлением понимают тот вариант,
который занимает минимальное число строчек,
то есть улучшает свойство \emph{обозримости} текста.

С другой стороны, принтер можно рассматривать как функцию,
которая на вход принимает
абстрактное или конкрентное синтаксическое дерево и дополнительные параметры,
а на выходе выдает текст. В случае, если на вход принтеру подается конкретное
синтаксическое дерево, то есть дерево разбора, принтер может быть частичной
функцией по отношению к синтаксическим конструкциям языка.
Такое ослабление связано
с тем, что для конструкций, на которых принтер неопределен, возможно использование
текстового представления, заложенного в дерево разбора.

Рассмотрим небольшой пример.
Пусть в СК задано условие вида: “последовательные операторы пишутся
на одной строке,
если помещаются в $N$ символов, а иначе --- на разных строках”.
На рис.~\ref{fig:seqImage} изображено синтаксическое дерево
последовательности двух операторов. Такое дерево, согласно заданному
правилу, может быть напечатано одним из
двух вариантов (рис.~\ref{fig:seqCode1}, ~\ref{fig:seqCode2}),
выбор происходит в зависимости от ширины вывода. Так, при ширине, равной
35 символов (длина строки
<<\lstinline[language = Java]{System.out.println("Hello world"); }>>),
должен выбираться вариант, изображенный на рис.~\ref{fig:seqCode2},
так как код на рис.~\ref{fig:seqCode1} имеет ширину более 35 символов.
Могут быть заданы и более сложные условия.

\begin{figure}[h!]
	\centering
	\includegraphics[width=0.8\textwidth]{seqTree}
	\caption{Последовательные операторы}
	\label{fig:seqImage}
\end{figure}

\begin{figure}[h!]
	\centering
	% \inputminted{c}{Podkopaev/codes/seqCode1.java}
	\lstinputlisting[language=Java]{Podkopaev/codes/seqCode1.java}
	\caption{Последовательные операторы в строчку}
	\label{fig:seqCode1}
\end{figure}

\begin{figure}[h!]
	\centering
	% \inputminted{c}{Podkopaev/codes/seqCode2.java}
	\lstinputlisting[language=Java]{Podkopaev/codes/seqCode2.java}
	\caption{Последовательные операторы в несколько строк}
	\label{fig:seqCode2}
\end{figure}


Рассмотрим другой пример.
Пусть нам нужно текстовое представление синтаксического дерева конструкции
“\lstinline{if}”, и заданы шаблоны c рис.~\ref{fig:ifTemplate2} и
\ref{fig:ifTemplate1}. При этом вариант, изображенный на
рис.~\ref{fig:ifTemplate2} выбирается только в случае, если условие и
ветки могут быть напечатаны в одну строчку.

\begin{figure}[h!]
	\subfloat[]{
		\lstinputlisting[language=Haskell]{Podkopaev/codes/ifTemplate2.hs}
		\label{fig:ifTemplate2}	
	}
	\quad
	\subfloat[]{
		\lstinputlisting[language=Haskell]{Podkopaev/codes/ifTemplate1.hs}
		\label{fig:ifTemplate1}	
	}
	\caption{Представления для конструкции “\lstinline{if}”}
	\label{fig:ifTemplateEx}	
\end{figure}


Тогда для деревьев, представленных на рис.
\ref{fig:ifImage1} и \ref{fig:ifImage2}, будут напечатаны тексты, представленные на
рис. \ref{fig:ifCode1} и \ref{fig:ifCode2} соответственно.

\begin{figure}[h!]
\centering
	\subfloat[]{
		\centering
		\includegraphics[width=0.6\textwidth]{if1}
		\label{fig:ifImage1}
	}
	\quad
	\subfloat[]{
		\centering
		% \inputminted{haskell}{Podkopaev/codes/ifCode1.hs}
		\lstinputlisting[language=Haskell]{Podkopaev/codes/ifCode1.hs}
		\label{fig:ifCode1}	
	}

	\caption{Использование представления с рис.~\ref{fig:ifTemplate2}}
\end{figure}

\begin{figure}[h!]
\centering
	\subfloat[]{
		\centering
		\includegraphics[width=0.6\textwidth]{if2}
		\label{fig:ifImage2}
	}
	\quad
	\subfloat[]{
		\centering
		% \inputminted{haskell}{Podkopaev/codes/ifCode1.hs}
		\lstinputlisting[language=Haskell]{Podkopaev/codes/ifCode2.hs}
		\label{fig:ifCode2}	
	}

	\caption{Использование представления с рис.~\ref{fig:ifTemplate1}}
\end{figure}

Существует несколько подходов к написанию принтеров.
Классическим способом задания принтеров в функциональных языках
программирования являются
принтер-комбинаторы~\cite{wadler, swierstra, swierstraChitil,
swierstra04, hughes, peytonJones, kiselyov, chitil, swiComb}.
Кроме того, существует работа, посвященная совместной разработке
принтера и синтаксического анализатора~\cite{rendelInvert}.
В~\cite{jongeEveryOccasion, jongeReengine, brandBox} описаны методы
создания принтеров с помощью специализированных грамматик.

К сожалению, принтеры, создаваемые с помощью упомянутых подходов,
слабопараметризуемы и сложны, поскольку приведенные
подходы недостаточно декларативны. Чтобы избежать подобных проблем,
принтеры можно задавать с помощью шаблонов, то есть примеров представления для
синтаксических конструкций, подобных приведенным на рис.~\ref{fig:ifTemplateEx}.
Принципиальная возможность
осуществления такого способа была доказана в рамках предыдущей работы
автора~\cite{CoursePaper}. В ней был разработан
обобщенный принтер для учебного языка L, использующий расширяемый
синтаксический анализатор целевого языка для получения шаблонов.

% Целью данной работы является разработка метода задания принтеров с помощью
% образцов для языков программирования. 
% Для апробирования метода было принято решение разработать принтер-плагин
% языка Java для среды разработки IntelliJ IDEA\footnote{\cd{http://www.jetbrains.com/idea/}}.
% В ходе разработки данного метода возникла необходимость улучшить существующую
% принтер-комбинаторную библиотеку\cite{swierstra}. 

Целью данной работы является разработка эффективной принтер-комбинаторной
библиотеки, которая может быть использована при создании принтеров, задаваемых
шаблонами, а также апробация самого подхода описания принтеров с помощью
шаблонов для языка Java.

\section{Обзор предметной области}

Одним из подходов к заданию принтеров являются принтер-комбинаторы.
В этой главе приведен обзор классических принтер-комбинаторов, а также
принтер-комбинаторов с дополнительным оператором \emph{выбора}, которые
в рамках данной работы использованы для реализации принтеров, задаваемых
с помощью шаблонов. Для решения проблем эффективности
комбинаторов с выбором в данной работе был использован подход BURS.
Апробация подхода задания принтеров с помощью шаблонов
была произведена для языка Java, для которого есть средства форматирования,
встроенные в IDE.

\subsection{Принтер-комбинаторы}

Базовыми принтер-комбинаторными библиотеками являются библиотеки
Джона Хьюза~\cite{hughes} и Филиппа Вадлера~\cite{wadler}, которые
представляют собой функциональную переработку алгоритма
Оппена~\cite{oppen}.
Ограничимся рассмотрением библиотеки Вадлера, так как
библиотека Хьюза обладает теми же свойствами, которые принципиальны в контексте
данной работы.

В библиотеке ключевым типом является документ.
Он представляет сущность, которая потом может
быть переведена в строковое представление алгоритмом принтера.
Основные конструкторы для составления документа таковы:
\begin{itemize}
  \item атомарная строка, которая печатается как есть;
  \item \emph{разделитель};
  \item последовательная композиция двух документов;
  \item набор связанных документов.
\end{itemize}

Определяющей особенностью данного подхода является то, что все разделители
в рамках одного набора могут быть совместно заменены алгоритмом принтера
на пробельный символ или на перевод строки. Выбор для каждого набора разделителей
основывается на том, что вывод должен поместиться в заданную ширину,
используя минимальное число строк.

Основная проблема такого подхода заключается в его слабой выразительной силе.
Документы, построенные по синтаксическому дереву печатаемой программы,
обрабатываются слишком единообразно, что иногда приводит к нежелательному результату.
Пусть, к примеру, нужно напечатать программу на языке
Python\footnote{\cd{http://python.org}}.
Между последовательными операторами в случае их печати на одной строчке необходимо
добавить дополнительный разделитель (``;''), иначе программа станет некорректной
(см. рис.~\ref{fig:seqEx}). Однако, описанные принтер-комбинаторы не предоставляют
возможности задать такое поведение.
Кроме того, с помощью таких принтер-комбинаторов невозможно выразить разные проектные СК,
так как они всегда печатают текст в одном стиле, который жестко ``зашит'' в их код.

\begin{figure}[h!]
	\centering
	\null\hfill
	\subfloat[Корректный код]{
		\centering
    \makebox[.4\textwidth] {
		  \lstinputlisting[language=Python]{Podkopaev/codes/pythonCode.py}
    }
	}
	\null\hfill
	\subfloat[Некорректный код]{
		\centering
    \makebox[.4\textwidth] {
	  	\lstinputlisting[language=Python]{Podkopaev/codes/pythonCodeBad.py}
    }
	}
	\hfill\null
	\caption{Пример работы принтер-комбинаторов для языка Python}
  \label{fig:seqEx}	
\end{figure}

Более подробный обзор библиотек Хьюза и Вадлера представлен в~\cite{CoursePaper}.

Большинство принтер-комбинаторных библиотек~\cite{
swierstraChitil, swierstra04, peytonJones, kiselyov, chitil}
являются развитиями работ Хьюза и Вадлера. Так, в отличие от базовых, среди
них есть реализации с линейной сложностью обработки документа от его размера и
\emph{online} алгоритмы, которые не требуют просмотра всего документа
для начала печати его текстового представления. Но все они обладают тем же
интерфейсом, а значит в них также неразрешимы задачи, в которых требуется
задавать варианты текстовых представлений, которые отличаются не только
пробелами и переводами строк.

\subsection{Принтер-комбинаторы с выбором}

Существенно от описанных выше отличаются библиотеки, предоставляющие в своем
интерфейсе комбинатор \emph{выбора}, который позволяет задавать для одного поддерева
принципиально разные варианты раскладок.
Так, в работах~\cite{jongeEveryOccasion, jongeReengine} используется
оператор \lstinline[language = Haskell]{ALT},
но алгоритм принтера устроен так, что среди двух альтернатив выбирается первая, если она
помещается в заданную ширину, и вторая --- иначе,
что не дает оптимальный результат на выходе.

Оптимальные принтер-комбинаторы с выбором были впервые представлены в работе~\cite{swierstra}.
Их реализация является частью Utrecht Tools
Library\footnote{\cd{http://www.cs.uu.nl/wiki/HUT/WebHome}}
(практическая реализация несколько изменена по
отношению к той, что описана в статье, но отличие несущественно).
В данном подходе текст строится из блоков прямоугольной формы с возможно неполной последней
строчкой (см. рис. \ref{fig:basicFormat}). В реализации на Haskell блоки представляются
структурой \lstinline[language = Haskell]{Format}:
\begin{lstlisting}[language=haskell]
    data Format = Elem { 
      height        :: Int
    , lastLineWidth :: Int
    , width         :: Int
    , txtstr        :: Int -> String -> String
    }
\end{lstlisting}

Первые три поля структуры определяют геометрические размеры блока, а последнее --- функция,
которая используется для преобразования блока в текст. Здесь используется функция, а не
просто строчка, чтобы можно было преобразовывать вложенные блоки за линейное время. Первый
аргумент \lstinline[language = Haskell]{txtstr} задает сдвиг блока.

\begin{figure}
  \centering
  \subfloat[Блок текста]{
    \raisebox{5mm}{
      \centering
      \vspace{0pt}
      \tikz{
        \draw (0,0) -- (1,0) -- (1,0.2) -- (2,0.2) -- (2,1) -- (0, 1) -- cycle;
      }
    }
    \label{fig:basicFormat}
  }
  ~
  \subfloat[Горизонтальная композиция]{
    \centering
    \tikz{
       \draw (0,0) -- (1,0) -- (1,0.2) -- (2,0.2) -- (2,1) -- (0, 1) -- cycle;
       \draw (1.1,-0.9) -- (2.1,-0.9) -- (2.1,-0.7) -- (3.1,-0.7) -- (3.1,0.1) -- (1.1,0.1) -- cycle;
     }
     \label{fig:beside}
  }
  %\hfill
  ~
  \subfloat[Вертикальная композиция]{
    \makebox[.28\textwidth] {
    \centering
    \tikz{
       \draw (0,0) -- (1,0) -- (1,0.2) -- (2,0.2) -- (2,1) -- (0, 1) -- cycle;
       \draw (0,-1.1) -- (1,-1.1) -- (1,-0.9) -- (2,-0.9) -- (2,-0.1) -- (0,-0.1) -- cycle;
    }
    \label{fig:above}
    }
  }
  \caption{Примитивы блока текста}
  \label{fig:basicConcat}
\end{figure}

Для работы с блоками текста используется следующие четыре примитива:
\begin{lstlisting}[language=haskell]
    s2fmt     :: String -> Format
    indentFmt :: Int -> Format -> Format
    aboveFmt  :: Format -> Format -> Format
    besideFmt :: Format -> Format -> Format
\end{lstlisting}

Функция \lstinline[language = Haskell]{s2fmt} создает блок текста,
состоящий из одной строчки; \lstinline[language = Haskell]{indentFmt} по блоку создает новый,
сдвинутый на заданное число позиций. Действие примитивов композиции
\lstinline[language = Haskell]{besideFmt} и \lstinline[language = Haskell]{aboveFmt}
показано на рис.~\ref{fig:beside} и \ref{fig:above} соответственно.

Также, как и в библиотеках без комбинатора выбора, в работе~\cite{swierstra} используется понятие
\emph{документа}. Здесь документ можно рассматривать как множество возможных раскладок
(набор \lstinline[language = Haskell]{Format}-элементов). Документы описываются типом
\lstinline[language = Haskell]{Doc}, экземпляры которого на этапе построения представляют собой
деревья применений приведенных ниже комбинаторов, а на этапе обработки алгоритмом
принтера им в соответствие ставится итоговое множество вариантов текстовых представлений.

Документ конструируется с помощью следующих комбинаторов, которые симметричны
примитивам построения блоков текста:
\begin{lstlisting}[language=haskell]
    text   :: String -> Doc
    indent :: Int -> Doc -> Doc
    beside :: Doc -> Doc -> Doc
    above  :: Doc -> Doc -> Doc
\end{lstlisting}

В дополнение появляется пятый комбинатор для документов:
\begin{lstlisting}[language=haskell]
    choice :: Doc -> Doc -> Doc
\end{lstlisting}

Этот комбинатор и является тем самым комбинатором выбора. Он представляет
\emph{объединение} множеств раскладок документов, которые были переданы как
аргументы комбинатора. Заметим, что только этот комбинатор может произвести
документ с несколькими раскладками из одновариантных аргументов.

Оригинальная реализация существенно опирается на ленивые вычисления. В~\cite{swierstra}
множество вариантов, соответствующее экземпляру \lstinline[language = Haskell]{Doc},
представляется ленивым списком всех возможных раскладок, удовлетворяющих ограничению
на максимальную ширину. Этот список отсортирован в порядке ``ухудшения''
раскладок, то есть в голове списка лежит ``лучшая'', в терминах оптимальности,
раскладка из возможных при заданной ширине. В случае
\lstinline{beside}- и
\lstinline{above}-композиций
документов полная (без учета ленивости) сложность вычисления списка нового документа
составляет $O(n \times m)$, где $n$ и $m$ --- размеры списков, соответствующих 
соединяемым документам. Размер нового списка также порядка $n \times m$.
Он не обязательно точно равен $n \times m$, так как некоторые из полученных
представлений могут не подпадать под ограничение на ширину, соответственно их можно
отбросить на этапе построения нового списка.

Выбор лучшего представления для самого верхнеуровнего документа происходит
просто --- нужно из соответствующего списка взять первый элемент.
Это создает впечатление, что общее число операций,
благодаря ленивым вычислениям, существенно уменьшается.
Но это не так из-за реализации обработки документа,
построенного с помощью комбинатора \lstinline[language = Haskell]{beside}, которая
вынуждает полное вычисление дочерних списков. Более того, из-за свойств отношения
порядка, построенного по критерию оптимальности, в рамках данной модели списков
принципиально нельзя построить ленивую обработку комбинатора
\lstinline[language = Haskell]{beside}.
Так, выбор оптимальной раскладки документа в~\cite{swierstra} имеет в худшем случае экспоненциальную 
сложность от числа комбинаторов, использованных при его построении.
В~\cite{swiComb} приведены оптимизации для данной модели, но они
не улучшают асимптотику решения для деревьев в общем случае.

\subsection{BURS}

Bottom-Up Rewrite System (BURS)~\cite{burs} --- это метод динамического
программирования на деревьях, изначально появившийся в контексте задачи выбора
инструкций для генерации машинного кода. Основой BURS является
регулярная грамматика с древовидными правилами~\cite{tata}, для которых задана
стоимость применения подстановки,
то есть грамматика со следующим набором правил: 

$$
\begin{array}{rcll}
  N &:& \alpha& [c]\\
  N &:& \alpha\; (K_1,\dots,K_n)& [c]
\end{array}
$$

Здесь $N, K_i$ это нетерминалы, $\alpha$ --- терминал,
$c$ --- функция стоимости, заданная для каждого правила.
Как и для обычной линейной грамматики, вводится стартовый
нетерминал S. Считается, что терминальное дерево выводится в
данной грамматике, если его можно получить с помощью правил
подстановки из одноузлового дерева $S$.
Каждая подстановка заменяет нетерминал $N$, находящийся в листе дерева, на дерево 
$\alpha\;(K_1,\dots,K_n)$, если в грамматике есть правило
$N:\alpha\;(K_1,\dots,K_n)$. 
Для каждой подстановки вычисляется стоимость ее применения с помощью
функции стоимости $c$.
Аргументами функции могут служить терминальная метка $\alpha$ и стоимости
вывода поддеревьев.
Задачей, которую решает BURS, является поиск вывода наименьшей стоимости
для заданного дерева по заданной грамматике.
Такой вывод может быть найден двухпроходным алгоритмом.

Первый проход (\emph{пометка}) обрабатывает дерево снизу вверх и вычисляет
для каждого узла набор троек $(K,\;R,\;c)$, где $K$ --- нетерминал, из которого может быть
выведено поддерево с корнем в обрабатываемом узле,
$R$ --- первое правило, которое используется для вывода минимальной стоимости из $K$,
$c$ --- стоимость такого вывода.
Процесс пометки происходит следующим образом:

\begin{itemize}
\item для листовой вершины, помеченной терминалом $\alpha$, в множество троек
этого вершины добавляется $(K,\;R,\;c\:(\alpha))$ для каждого правила $R=K:\;\alpha\;[c]$;
\item для промежуточной вершины, помеченной терминалом $\alpha$,
с непосредственными поддеревьями $v_1,\dots,v_n$
в множество добавляется тройка $(K,\;R,\;c\:(\alpha,c_1,\dots,c_n))$ для каждого правила
$R=K:\;\alpha\;(K_1,\dots,K_n)\;[c]$, где $(K_i,\;R_i,\;c_i)$ входит в множество троек для
$v_i$; если есть несколько правил вывода из нетерминала $K$, то выбирается правило,
минимизирующее стоимость вывода.
\end{itemize}

Второй проход (\emph{свертка}) просматривает дерево сверху вниз, используя сделанные пометки.
Первое правило из минимального вывода определяется тройкой $(S,\;R,\;c)$ для корневого узла
(если такой тройки нет, то вывод из $S$ невозможен).
Это правило однозначно определяет нетерминалы $K_i$ для каждого непосредственного поддерева
и процесс повторяется.

Для пометки дерева потенциально необходимо каждое правило грамматики применить к каждому узлу.
При фиксированной грамматике алгоритмическая сложность первого прохода --- $O\:(|R|)$,
где $|R|$ --- количество правил
(размер множества троек для каждого узла ограничен числом нетерминалов, которое не больше,
чем количество правил). Свертка также имеет линейную сложность.


\subsection{Средства форматирования кода в IDE}

Интегрированные среды разработки программного обеспечения
(IDE) предоставляют средства
для форматирования программного кода. Рассмотрим их на примере двух Java IDE ---
IntelliJ IDEA\footnote{\cd{http://jetbrains.com/idea/}} и
Eclipse\footnote{\cd{http://eclipse.org}}.
Для задания требуемого СК используется широкий набор настроек \emph{форматтера},
подпрограммы IDE, отвечающей за форматирование исходных текстов.
Примерами таких настроек являются:
\begin{itemize}
  \item помещать ли фигурную скобку на той же строке, что и
    предыдущее выражение;
  \item форматирование списков --- всегда на одной строчке, переводить строчку после
    каждого элемента или печатать на одной строке,
    пока строчка меньше заданной рекомендуемой ширины.
%   \item и т.д.
\end{itemize}
На рис. ~\ref{fig:ideaFormatter} и~\ref{fig:eclipseFormatter} приведены диалоги задания
параметров форматирования в IntelliJ IDEA и Eclipse соответственно.

\begin{figure}[p]
	\centering
	\includegraphics[width=\textwidth]{ideaFormatter}
	\caption{Окно настройки форматтера IntelliJ IDEA}
	\label{fig:ideaFormatter}
\end{figure}

\begin{figure}[p]
	\centering
	\includegraphics[width=\textwidth]{eclipseFormatter}
	\caption{Окно настройки форматтера Eclipse}
	\label{fig:eclipseFormatter}
\end{figure}

У встроенных форматтеров есть следующие особенности.
Во-первых, это невозможность выразить
нестандартный СК, так как настройки форматтеров, несмотря на их большое
количество,
дают ограниченную вариативность для текстовых представлений форматируемых
программ. В целом, количество принципиально разных
стилей форматирования, которые можно задать с помощью данных настроек,
невелико.
Во-вторых, в случае, если надо
придерживаться СК уже существующего проекта, то по коду этого проекта необходимо
вручную задать все настройки форматтера.
Причем наборы настроек в разных IDE не совпадают, что увеличивает сложность
поддержки единого СК, если разработчики используют отличные от друг друга IDE.
Для решения данной проблемы существуют плагины, позволяющие использовать
внешние фоматтеры\footnote{\cd{http://plugins.jetbrains.com/plugin/6546}}.
Кроме того, есть средства, позволяющие экспортировать настройки форматтера в
XML-файл для их использования в другой
IDE\footnote{\cd{http://blog.jetbrains.com/idea/2014/01/ intellij-idea-13-importing-code-formatter-settings\-from-eclipse/}}.

Важным достоинством описанных форматтеров является малое время работы.
Это достигается в том числе и за счет того, что часто форматируется не весь
файл, а только его часть (см.~\cite{eclipse}),
и из-за детерминированности представлений узлов синтаксического дерева,
которая следует из специфики настроек форматтера.
Однако форматирование целого большого проекта занимает существенное время.
Например, обработка кода IntelliJ IDEA Community Edition занимает более часа
у встроенного в IDEA форматтера.

\section{Реализация}

Контекстом данной работы является разработка метода задания принтеров с помощью шаблонов.
Под \emph{шаблоном} здесь и далее понимаются данные, сопоставляя которые с
переданным на печать синтаксическим деревом, мы будем получать текстовое представление
для этого дерева. Более точно, каждый конкретный шаблон позволяет построить
текстовые представления для подходящего по типу 
узла синтаксического дерева, используя уже полученные представления дочерних поддеревьев.

Фактически в реализации шаблон --- это размеченное дерево разбора
некоторой синтаксической конструкции, в котором по каждой метке можно выяснить
ограничения на представление соответствующих поддеревьев и описание, каким
образом нужная раскладка поддерева должна быть вставлена в шаблон.
При этом сами шаблоны получаются из некоторого эталонного репозитория с исходном
кодом на целевом языке определяемого принтера.
Так, к примеру, принтер будет использовать форматирование GNU, если ему на вход
передать один или несколько проектов в СК GNU.

Кроме того, полученный таким образом принтер должен выдавать оптимальное представление
для синтаксического дерева, переданного на печать. На нижнем уровне в принтере 
используются оптимальные принтер-комбинаторы с выбором. Здесь комбинатор выбора нужен
для возможности задания вариантов представления, соответствующих разным шаблонам.
Недостатком существующих оптимальных принтер-комбинаторов с выбором~\cite{swierstra}
является их экспоненциальная сложность. Поэтому для возможности использования того же
комбинаторного интерфейса в рамках данной работы с помощью BURS была разработана
полиномиальная версия этих комбинаторов~\cite{podkopaevBoulytchev}.

Для апробации метода в случае языка Java был разработан принтер-плагин для
IntelliJ IDEA, что позволило переиспользовать синтаксический анализатор Java
для получения шаблонов.
Разработка велась на языке Kotlin.
Kotlin\footnote{\cd{http://kotlin.jetbrains.org/}}
--- это функциональный, объектно-ориентированный, компилируемый
в JVM-байткод и JavaScript язык, разрабатываемый компанией
JetBrains\footnote{\cd{http://jetbrains.org/}}.
Kotlin был выбран для реализации принтер-плагина к IntelliJ IDEA по нескольким
причинам. 
Во-первых, Kotlin обладает хорошей интеграцией с Java, что позволяет
использовать его с IDEA API. 
Во-вторых, функции в Kotlin являются объектами первого рода, что позволяет
легко реализовывать комбинаторные библиотеки на нем.
На данный момент Kotlin находится в стадии разработки, поэтому
периодически возникают
проблемы с тем, что исходные коды перестают быть совместимыми с новыми
версиями языка,
но обычно требуется внести небольшой набор исправлений для
восстановления работоспособности.

% \subsection{Полиномиальной сложности принтер-комбинаторы с выбором}

\subsection{Оптимальное форматирование как задача BURS}

Для снижения алгоритмической сложности задачи поиска
оптимального представления документа, заданного комбинаторами из~\cite{swierstra},
можно произвести сведение к BURS.
Сведение основано на следующих наблюдениях.
Пусть $w$ есть максимальная допустимая
ширина вывода. Поскольку каждая возникающая раскладка представляется блоком
текста, для поиска оптимального представления можно рассматривать
все промежуточные раскладки
как тройки $(n, k, h)$, где $n \le w$ --- это общая ширина раскладки, $k \le n$ ---
ширина ее последней строчки, $h$ --- ее высота. Тогда очевидно, что при $h_1 \le h_2$
между $(n, k, h_1)$ и $(n, k, h_2)$ первая тройка предпочтительней на любом этапе вычислений.
Таким образом для каждого узла не может быть более $w^2$ существенных представлений\footnote{
На самом деле, из-за ограничения $k \le n$ максимальное число раскладок не $w^2$, a
$\frac{w^2 + w}{2}$, но это несущественно.}.

Документ, для которого мы ищем раскладку, можно рассматривать как дерево, построенное из примитивов
\lstinline[language=Haskell]{text},
\lstinline[language=Haskell]{indent},
\lstinline[language=Haskell]{beside},
\lstinline[language=Haskell]{above} и \lstinline[language=Haskell]{choice}. Тогда задачу
раскладки документа можно решать независимо для поддеревьев, а потом объединять решения
при учете, что для каждого поддерева
и каждой пары $(n, k), k \le n \le w$ запоминается такая минимальная $h$, что для поддерева существует
текстовое представление с размерами $(n, k, h)$. Тогда, совершив обход дерева снизу вверх, мы сможем
вычислить оптимальное представление для всего дерева. Полезно заметить,
что оптимальное представление дерева не всегда получается из оптимальных представлений его
поддеревьев, поскольку при использовании поддеревьев возникают дополнительные
ограничения на ширину раскладок этих поддеревьев.

Приведенные наблюдения можно формализовать в виде BURS-задачи.
Для заданной ширины вывода $w$ введем набор нетерминалов
$T_n^k$, для всех $k \le n \le w$. Определим BURS-грамматику так, чтобы цена вывода $h$ нетерминала
$T_n^k$ для документа соответствовала его раскладке с параметрами $(n, k, h)$.
Для такой BURS-грамматики этап разметки посчитает все существенные раскладки, а этап свертки
вернет оптимальную. Определим правила переписывания для этой грамматики:
\begin{enumerate}
\item Для терминального узла $[\mbox{\lstinline{text s}}]$\footnote{
  Квадратные скобки используются для обозначения терминалов, состоящих из одного
  или нескольких символов.}
  существует два варианта:
  \begin{itemize}
     \item Если $|s|\le w$ (где $|s|$ --- это длина строки $s$), то вводится единственное правило
           $T^{|s|}_{|s|}: [\mbox{\lstinline{text s}}]$ со стоимостью $1$;           
           для всех остальных
           $k, n\ne |s|$ используется $T^k_n:[\mbox{\lstinline{text s}}]$ со стоимостью $\infty$;
     \item Если $|s| > w$, то вводится правило $T^k_n:[\mbox{\lstinline{text s}}]$ со стоимостью\
       $\infty$ для всех $k, n$.
  \end{itemize}
  Действительно, раскладка документа, состоящего из строчки длины $|s|$, может быть только размеров
  $(|s|, |s|, 1)$. Все остальные размеры недоступны, поэтому имеют стоимости $\infty$.

\item Для узла $[\mbox{\lstinline{indent m}}]$ введем два набора правил:
  \begin{enumerate}
     \item $T^{k+m}_{n+m}:[\mbox{\lstinline{indent m}}]\:(T^k_n)$ со стоимостью,
       равной стоимости раскладки поддерева $m$ в $T_n^k$, для всех $n$ 
     и $k$ таких, что $n+m\le w$ и $k\le n$;
     \item $T^k_n:[\mbox{\lstinline{indent m}}]\:(T^i_j)$ со стоимостью $\infty$ в противном случае.
  \end{enumerate}
  Понятно, что сдвиг раскладки с параметрами $n$, $k$ и $h$ на $m$ позиций вправо
  создает раскладку с параметрами $n+m$, $k+m$, $h$. Такая раскладка допустима, если
  $n+m\le w$ и $k+m\le w$.

\item Для узла $[\mbox{\lstinline{above}}]$ вводим правило $T^{k_2}_{\max(n_1, n_2)}:[\mbox{\lstinline{above}}]\:(T^{k_1}_{n_1},\;T^{k_2}_{n_2})$ 
со стоимостью, равной сумме стоимостей вывода поддеревьев,
для всех $k_1\le n_1\le w$ и $k_2 \le n_2 \le w$.

Действительно, при вертикальном соединении раскладок с параметрами
$n_1$, $k_1$, $h_1$ и $n_2$, $k_2$, $h_2$ мы получаем раскладку с размерами
$\max\:(n_1,n_2)$, $k_2$, $h_1+h_2$. Вертикальная композиция допустимых раскладок всегда допустима.

\item Для узла $[\mbox{\lstinline{beside}}]$ вводим правило
  $T^{k_1+k_2}_{\max\:(n_1,\:k_1+n_2)}:[\mbox{\lstinline{beside}}]\:(T^{k_1}_{n_1},\:T^{k_2}_{n_2})$
  для каждой комбинации $n_1, n_2, k_1, k_2$ такой, что $k_1+k_2\le\max\:(n_1,\:k_1+n_2)\le w$.
  Стоимость такого вывода равна сумме стоимостей вывода поддеревьев минус 1.
  Это может быть легко проверено из геометрических соображений.

\item Для узла $[\mbox{\lstinline{choice}}]$ вводим правило
  $T^k_n:[\mbox{\lstinline{choice}}]\:(T^k_n,\:T^k_n)$ для всех $k\le n\le w$.

  Цена есть минимум среди цен вывода для поддеревьев. Понятно, что среди двух раскладок
  с одинаковыми ширинами выбирается та, что имеет меньшую высоту.
\end{enumerate}

Для завершения описания грамматики необходимо ввести правило для стартового нетерминала $S$.
Можно добавить правило $S : r$ с тождественной функцией цены для любого $r$, или ввести
цепное правило $S: T_n^k$ с такой же функцией для всех нетерминалов $T_n^k$
(такое правило требует несущественного расширения определения BURS).

Число нетерминалов в определенной выше грамматике равно $w^2$.
Однако, число правил есть $O(w^4)$, так
как в дереве есть узлы со степенью 2. Так, приведенная BURS-реализация оптимального принтера
работает за линейное время от числа узлов в дереве документа для фиксированной ширины вывода, при
этом сложность от ширины вывода есть $O(w^4)$. Понятно, что данное сведение может быть выполнено и
для других примитивов построения дерева, которые могут иметь большую степень, но ценой
экспоненциального роста сложности по $w$.
\label{txt:bursReduction}

\subsection{Реализация сведения задачи оптимального форматирования к BURS}

В рамках данной работы была реализована
принтер-комбинаторная библиотека на языке
Haskell\footnote{\cd{http://github.com/anlun/polynomialPPCombinators}}
(см. приложение)
с тем же набором комбинаторов,
что и в~\cite{swierstra},
которая линейна относительно входного документа и полиномиальна
относительно максимальной ширины вывода за счет описанного выше сведения задачи к BURS.
Данная реализация использует низкоуровневые типы и функции из оригинальной
библиотеки~\cite{swierstra}, в то время как высокоуровневые типы и комбинаторы переопределены.

В реализации нет непосредственного использования BURS: в явном виде не задается BURS-грамматика,
нет набора нетерминалов и стандартного алгоритма обработки.
Вместо этого для каждого узла документа вычисляется ассоциативный массив, который
ставит в соответствие паре $(n, k)$ лучший (минимальный по числу строк) блок текста с параметрами
ширин $n$ и $k$. Так, в ассоциативном массиве записаны пары $((n, k), f)$, где $f$ --- это
блок текста, соответствующий оптимальному представлению с ширинами $(n, k)$. Значение
высоты $f$ есть минимальная стоимость вывода нетерминала $T^k_n$ для данного узла.
Заметим, что поскольку $f$ является конечным результатом для $T^k_n$, а не просто
последним правилом, которое нужно применить для построения ответа, то отменяется
необходимость применения в дальнейшем алгоритма свертки.
В конце, для корня дерева, представляющего документ, из
ассоциативного массива выбирается элемент минимальной стоимости.

Наибольший интерес в рамках данного исследования представляет поведение библиотеки
в худшем случае.
Реализация была апробирована на документах, полученных с помощью
функции генерации, приведенной на рис.~\ref{fig:treeToDocMy}. Они достаточно
``плохи'', поскольку активно используют комбинаторы
\lstinline[language= Haskell]{beside} и
\lstinline[language= Haskell]{choice}, что должно приводит к экспоненциальной зависимости
числа нефакторизованных раскладок от размера дерева комбинаторов.
В функции генерации используются операторы
\lstinline[language= Haskell]{(>|<)},
\lstinline[language= Haskell]{(>-<)},
\lstinline[language= Haskell]{(>//<)}, которые являются инфиксными синонимами для
комбинаторов
\lstinline[language= Haskell]{beside},
\lstinline[language= Haskell]{above} и
\lstinline[language= Haskell]{choice} соответственно.

\begin{figure}[h!]
  \lstinputlisting[language = Haskell]{Podkopaev/codes/AltPrettyTest.hs}
  \caption{Функция генерации деревьев для тестов производительности}
  \label{fig:treeToDocMy}
\end{figure}

Результаты времени исполнения для сравнения авторской реализации с оригинальной библиотекой
приведены в таблице~\ref{tbl:time}.
Из приведенных данных видно, что, начиная с некоторой комбинации ширины вывода и размера документа,
библиотека~\cite{swierstra} не может вычислить раскладку документа.
Значения, записанные подобно \mbox{``-($>$ 59)''}, обозначают,
что после указанного времени процесс аварийно завершился с переполнением стека.

Авторская реализация часто не показывает линейное поведение, как это ожидается при фактическом
учетверении числа узлов в документе от строчки к строчке. Дополнительные эксперименты показали
связь данного поведения с разреженностью ассоциативного массива для больших ширин.
Другими словами, для маленьких деревьев число значений в соответствующем ассоциативном массиве
сильно меньше верхней границы. С ростом размера дерева число записей растет быстрее, чем
с линейной скоростью, пока не будут достигнуты значения, близкие к верхней границе.

Кроме того, особенностью описанной реализации является то, что она не использует 
ленивые вычисления для ускорения построения оптимального текстового представления для
поданного на вход документа, а, наоборот,
форсирует большинство вычислений, что делает ее легко переносимой на языки
без встроенной ленивости.

\begin{table}
	\centering
	\subfloat[Ширина вывода 25] {
		\centering
		\begin{tabular}{c c c}
		Число узлов & Оригинальная & Авторская \\ 
		\hline
		10921 & 0.07 & 0.18 \\
		43689 & 1.28 & 0.73 \\
		174761 & 6.47 & 2.86 \\
		699049 & 18.46 & 11.58 \\
		2796201 & 46.54 & 47.52 \\
		11184809 & 98.85 & 187.90 
		\end{tabular}
	}
	\quad
	\subfloat[Ширина вывода 50] {
		\centering
		\begin{tabular}{c c c}
		Число узлов & Оригинальная & Авторская \\ 
		\hline
		10921 & 0.12 & 0.69 \\
		43689 & 287.55 & 4.03 \\
		174761 & - (\textgreater 294) & 17.93 \\
		699049 & - (\textgreater 284) & 71.70 \\
                \phantom{ }&&\\
                \phantom{ }&&
		\end{tabular}
	}

	\quad
	\subfloat[Ширина вывода 100] {
		\centering
		\begin{tabular}{c c c}
		Число узлов & Оригинальная & Авторская \\
		\hline
		10921 & 0.06 & 0.97 \\
		43689 & 97.79 & 14.92 \\
		174761 & - (\textgreater 179) & 88.71 
		\end{tabular}	
	}
	\quad
	\subfloat[Ширина вывода 150] {
		\centering
		\begin{tabular}{c c c}
		Число узлов & Оригинальная & Авторская \\ 
		\hline
		10921 & 0.06 & 1.01 \\
		43689 & 38.99 & 20.75 \\
		174761 & - (\textgreater 59) & 204.51 
		\end{tabular}	
	}

	\caption{Время вычисления раскладки (в секундах)}
	\label{tbl:time}
\end{table}

\subsection{Расширение принтер-комбинаторов}

Для дальнейшего использования в принтер-плагине авторская библиотека комбинаторов
была переписана на язык Kotlin.
Эта реализация расширяет набор комбинаторов и использует
дополнительные техники, которые важны при практическом применении библиотеки в
контексте принтеров, задаваемых шаблонами.

\subsubsection{Мемоизация вычислений для поддеревьев.}

В реальных принтерах документы, состоящие из комбинаторов
\lstinline[language=Haskell]{text},
\lstinline[language=Haskell]{indent},
\lstinline[language=Haskell]{beside},
\lstinline[language=Haskell]{above} и \lstinline[language=Haskell]{choice}, чаще всего
представляют собой не дерево, а \emph{дэг} (DAG, Direct Acyclic Graph). Поэтому при наивной
реализации можно получить экспоненциальную сложность от размеров документа,
поскольку соответствующее дерево будет иметь экспоненциальный размер от размера дэга.
Чтобы избежать этой проблемы достаточно завести ассоциативный массив,
который будет хранить посчитанный набор раскладок по конкретному поддереву.
Кроме того, при наивной реализации данной оптимизации
алгоритм вычисления раскладки становится квадратичным от размера дэга,
так как вычисление хэша, используемого ассоциативным массивом, для дерева занимает
линейное время. Чтобы преодолеть и эту сложность, в дереве хранится вычисленный хэш.

\subsubsection{Комбинатор \lstinline{fill}.}

Для реализации принтера, использующего шаблоны, в библиотеку необходимо добавить
дополнительный принтер-комбинатор --- комбинатор \lstinline{fill}.

\begin{figure}[h!]
  \centering
	\subfloat[]{
		\centering
    \tikz[scale = 2.5]{
       \draw (0,0) -- (1,0) -- (1,0.2) -- (2,0.2) -- (2,1) --
          (0, 1) -- cycle;
       \draw (0,-0.1) -- (0,-1.1) -- (1.1,-1.1) -- (1.1,-0.9) --
          (2.3,-0.9) -- (2.3, 0.1) -- (1.1,0.1) -- (1.1,-0.1) -- cycle;
    }
		\label{fig:fill1}
	}
	\quad
  \subfloat[][fc --- константа сдвига]{
		\centering
    \tikz[scale = 2.5]{
          \draw (0,0) -- (1,0) -- (1,0.2) -- (2,0.2) -- (2,1)
            -- (0, 1) -- cycle;
          \draw (0.3,-0.1) -- (0.3,-1.1) -- (1.1,-1.1) -- (1.1,-0.9)
            -- (2.3,-0.9) -- (2.3, 0.1) -- (1.1,0.1) -- (1.1,-0.1) -- cycle;
          \draw[<->] (0,-0.6) -- (0.3,-0.6);
          \draw (0.15,-0.4) node [fill=white] {\tiny fc};
          \draw[dashed] (0,0) -- (0,-1.1);
       }
		\label{fig:fill2}
	}
	\caption{Оператор Fill}
\end{figure}

В качестве примера, показывающего необходимость такого комбинатора, рассмотрим
печать метода из языка Java. Пусть нам нужно получить на выходе следующий программный
код:

\lstinputlisting[language = Java]{Podkopaev/codes/codeBlockEx.java}

По описанному раннее подходу, для построения общей раскладки необходимо иметь представления
поддеревьев. В частности, представление тела метода:

\lstinputlisting[language = Java]{Podkopaev/codes/justBlockEx.java}

Тогда для реализации соответствующего соединения, представленного ниже,
необходим комбинатор \lstinline{fill}:

\lstinputlisting[language = Java]{Podkopaev/codes/codeBlockTemplateEx.java}

К сожалению, введение нового комбинатора накладывает дополнительные ограничения на
факторизацию. Это связано с тем, что теперь по парам $(n, k)$, где $n$ --- общая ширина,
а $k$ --- ширина последней строчки, нельзя однозначным образом выдать соответствующую
пару для раскладки соединения двух блоков. Так, при применении \lstinline{fill}-комбинатора
важной становится и ширина первой строчки нижнего блока, поскольку сумма ее и ширины
последней строчки верхнего блока могут дать максимум общей ширины. Таким образом,
у нетерминалов из BURS-сведения появляется дополнительный индекс, а их число
увеличивается с $w^2$ до $w^3$. Аналогично, количество правил перехода возрастает
с $O(w^4)$ до $O(w^6)$.

\subsubsection{Дополнительная фильтрация вариантов.}

Для того, чтобы избежать экспоненциальной сложности вычисления оптимальной
раскладки документа, мы ввели факторизацию по размерам (ширинам) текстового
представления.
Количество раскладок для каждого поддерева теперь ограничено, но, к сожалению,
слишком большой константой --- $w^3$ ($w^2$ для набора комбинаторов без
\lstinline{fill}), а сложность вычисления узлов
\lstinline{beside}, \lstinline{above}, \lstinline{fill} --- $O(w^6)$
($O(w^4)$ без комбинатора \lstinline{fill}). Факторизация была основана на том факте, что
среди раскладок с одинаковыми ширинами в любом дальнейшем использовании
к лучшему результату приводит вариант с меньшей высотой.
Для дополнительной фильтрации множества
вариантов воспользуемся рассуждением, что если раскладка $A$ обладает и
меньшими ширинами, и меньшей высотой, чем раскладка $B$, то, аналогично
предыдущей факторизации,
достаточно оставить только ее во множестве вариантов.

Таким образом мы ввели отношение частичного порядка на раскладках, а
описанная фильтрация --- поиск минимумов на частично упорядоченном
множестве представлений~\cite{poset}.
Очевидная реализация поиска имеет квадратичную сложность от размера множества,
таким образом асимптотика алгоритма не ухудшается из-за данной фильтрации.
К сожалению, эта оптимизация и не улучшает поведение
в худшем случае, так как
можно привести пример, когда все множество раскладок с допустимыми ширинами
будет состоять из несравнимых элементов, но на практике количество вариантов
существенно сокращается, что делает весь подход применимым на реальных данных.

\begin{figure}[t]
   \centering
    \makebox[0.15\textwidth]{
      \lstinputlisting[language = Java]{Podkopaev/codes/ifTemplate.java}
    }
  \caption{Шаблон конструкции \lstinline{if}}
  \label{fig:ifTemplate}
\end{figure}

\begin{figure}[t]
  \subfloat[Условие]{
    \makebox[0.15\textwidth]{
      \centering
      \lstinputlisting[language = Java]{Podkopaev/codes/ifCond.java}
    }
    \label{fig:ifCond}
  }
  \quad\quad
  \subfloat[Первая ветка]{
    \makebox[0.3\textwidth]{
      \centering
      \lstinputlisting[language = Java]{Podkopaev/codes/ifThen.java}
    }
    \label{fig:ifThen}
  }
  \quad\quad\quad
  \subfloat[Вторая ветка]{
    \makebox[0.3\textwidth]{
      \centering
      \lstinputlisting[language = Java]{Podkopaev/codes/ifElse.java}
    }
    \label{fig:ifElse}
  }
  \caption{Пример входных данных для построения представления конструкции \lstinline{if}}
  \label{fig:ifEx}
\end{figure}

\subsubsection{Вставка в шаблон.}
\label{txt:templateInsert}

В шаблонном подходе результат печати для узла синтаксического дерева строится
за счет вставки представлений его поддеревьев в текст шаблона.
Рассмотрим построение раскладки для конструкции
\lstinline{if}. У этой конструкции в общем случае три поддерева: условие,
ветка, соответствующая выполнению условия, и ветка, соответствующая
невыполнению условия.
На рис.~\ref{fig:ifTemplate} и \ref{fig:ifEx} представлен пример шаблона и представлений поддеревьев для
конструкции \lstinline{if}.

В шаблоне места для поддеревьев выделены блоками. Свойства этих блоков задают
ограничения на использование представлений соответствующих поддеревьев.
Так, в данном случае для каждого из них верно,
что представление, применяемое для вставки, может быть многострочным. Блок, связанный
с поддеревом условия, помимо этого также задает использование комбинатора
\lstinline{fill} с константой сдвига, соответствующей положению начала
второй строчки блока относительно родительского узла.
При использовании шаблона и представлений
поддеревьев с рис.~\ref{fig:ifEx} получается следующий результат:

%\begin{figure}[h!]
  \lstinputlisting[language = Java]{Podkopaev/codes/ifResult.java}
 % \caption{Результат вставки в шаблон}
  %\label{fig:templateResult}
%\end{figure}

При наивной реализации сложность вставки в шаблон есть
$O(w^{3\times n})$, где $w$ --- максимальная ширина вывода,
а $n$ --- число дочерних поддеревьев обрабатываемого узла,
поскольку каждое из поддеревьев может иметь $w^3$ различных
представлений после факторизации.
Однако, за счет инкрементальной реализации вставки
можно получить сложность $O(n \times w^6)$.
Для этого надо разбить шаблон на список, в котором элементы соответствуют
либо месту вставки поддерева, либо независимому тексту шаблона. Так, шаблон
с рис.~\ref{fig:ifTemplate} представляется списком:
\begin{itemize}
  \item ``\lstinline{if (}'';
  \item место условия;
  \item ``) \{'';
  \item место первой ветки;
  \item ``\} \lstinline{else} \{'';
  \item место второй ветки;
  \item ``\}''.
\end{itemize}

После над этим списком можно произвести свертку. При этом к аккумулятору на каждом
шаге будет присоединяться представление нового элемента списка с помощью
комбинаторов \lstinline{beside}, \lstinline{above} или \lstinline{fill}. 
В таком случае аккумулятор всегда будет содержать не более
$w^3$ представлений, как и каждый элемент обрабатываемого списка.
Поэтому операция присоединения
на каждом шаге будет иметь сложность $O(w^6)$, а вся вставка ---
$O(n \times w^6)$, так как количество участков текста не более чем $n + 1$, а значит
списочное представление шаблона имеет размер не более $2 \times n + 1$.

\subsection{Принтер-плагин языка Java для IntelliJ IDEA}

Работа принтер-плагина разбивается на два этапа: подготовка шаблонов и непосредственно
печать синтаксического дерева.

Для получения шаблонов алгоритм проходит по переданному пользователем репозиторию с
эталонным исходным кодом. По каждому узлу деревьев разбора файлов из репозитория
строится шаблон соответствующей синтаксической конструкции. Важной особенностью
метода в целом
является то, что для дальнейшей печати конструкций, имеющих плавающие число
поддеревьев, необходимо иметь отдельный шаблон для каждой комбинации поддеревьев.
Так, к примеру, для конструкции \lstinline[language = Java]{if} языка Java
необходимо иметь не менее двух шаблонов --- с веткой \lstinline[language = Java]{else}
и без нее. В данном случае такое требование не кажется слишком обременительным, но
если рассмотреть случай Java-класса, то ситуация несколько хуже --- у него может не
быть списка модификаторов доступа, суперкласса и реализуемых интерфейсов.
Это серьезное ограничение, но его невозможно обойти в рамках данного подхода,
поскольку единственной информацией о представлении конструкций должны быть
полученные шаблоны.

Вычисление текстового представления переданного на вход синтаксического
дерева происходит путем восходящего переписывания. Для каждого узла строится множество
возможных раскладок (набор блоков текста) по тем же правилам факторизации, чтобы были
применены для комбинаторной библиотеки. В дальнейшем представления поддеревьев
используются для подстановки в шаблоны родительского узла, что на выходе дает
набор раскладок для него. Шаблоны в данном контексте можно рассматривать как
BURS-правила.
Однако, несмотря на то, что число детей у родительского узла может
быть велико (в случае некоторых конструкций языка Java более 5),
это не приводит к экспоненциальному росту сложности по ширине вывода, которые
следуют из рассуждений раздела \ref{txt:bursReduction}, благодаря технике, описанной
в разделе \ref{txt:templateInsert}. Эта техника позволяет проводить подстановку
раскладок за 
$O(n \times w^{6})$ для любого $n \geq 2$ ($O(w^{3})$ для $n = 1$), где
$w$ --- ширина вывода, а $n$ --- число дочерних поддеревьев обрабатываемого узла.
Таким образом, сложность вычисления сушественных раскладок для узла дерева
составляет $O(t \times n \times w^{6})$, где $t$ --- общее число шаблонов,
а в целом поиск оптимального представления всего синтаксического дерева, переданного
на форматирование, занимает $O(m \times t \times n \times w^{6})$, где $m$
--- количество узлов в дереве.


Стоит заметить, что с инженерной точки зрения для решения отдельно стоящей задачи
форматирования по образцу кода на Java в IntelliJ IDEA лучше подходит
получение настроек для существующего форматтера с помощью известных техник обучения.
Подобный подход используется в работе~\cite{learning}.
Но описанный в данной работе метод позволяет выразить представления, которые не
предусмотрены встроенным форматтером, кроме того потенциально предоставляет
возможность проще создавать принтеры для новых языков. 

\subsubsection{Практические особенности получения и использования шаблонов.}

Поскольку каждый узел дерева разбора из эталонного репозитория порождает
шаблон, то частой ситуацией является присутствие шаблонов, которые функционально
неотличимы. Их наличие ухудшает время работы принтера, так как повторяются
аналогичные переходы от представлений поддеревьев обрабатываемого узла, приводящие
к одному и тому же результату. Чтобы избежать данной проблемы достаточно
отождествить шаблоны, обладающие одинаковым функциональном поведением.
На практике это было реализовано в виде факторизации по текстовому представлению
шаблона, в котором на месте меток записана информация об ограничении на раскладки
соответствующих поддеревьев.

Противоположную проблему создают шаблоны, получаемые из уникальных,
встречаемых только в специальном контексте представлений.
Так, рассмотрим шаблоны для поля класса Java,
получаемые из следующего текста:

\lstinputlisting[language = Java]{Podkopaev/codes/fieldsT1.java}

Здесь на выходе получается один и тот же факторизованный шаблон.
Несколько изменим пример. Пусть теперь
в эталонном коде было сделано дополнительное выравнивание по типам
и модификаторам доступа:

\lstinputlisting[language = Java]{Podkopaev/codes/fieldsT2.java}

По такому эталону получается три разных шаблона, каждый из которых не может
быть использован в произвольном случае. Кроме того, так как подход в целом не
умеет представлять поддеревья в зависимости от контекста, то полученные шаблоны
бесполезны и вредны. Поэтому для борьбы с подобными ситуациями имеет смысл
предпочитать то представление, что было получено из факторизованного шаблона с
наибольшим \emph{весом}, где под весом понимается встречаемость шаблона в
эталонном тексте.

\subsubsection{Обработка списочных структур.}

Особую сложность для представленного метода имеет
печать синтаксических структур с переменным, неограниченным числом
подвыражений. К примеру, это списки и бинарные выражения. Проблема вызвана
неясностью в том, как для таких структур задавать шаблоны. Можно хранить
представления для списков по количеству элементов
до некоторой максимальной длины, но,
во-первых, это достаточно обременительно, учитывая количество разнообразных
типов списков, а, во-вторых, такой подход не сможет работать на списках большей
длины. В рамках данной работы было реализовано два разных решения для этой
задачи: классический, применяемый форматтерами из IDE, и с использованием
шаблона для пары элементов списка.

Классический способ решения проблемы заключается в том, что
списки просто печатаются заполняющим методом (см. рис.~\ref{fig:listFill}),
то есть перевод строки происходит
в случае, когда следующий элемент уже не помешается на строчку, или каждый
новый элемент печатается на новой строчке (см. рис.~\ref{fig:listEveryLine}).
Кроме того, обычно позиция разделителя относительно элемента списка жестко
``зашита'' в форматтер --- к примеру,
запятая в списке параметров функции идет сразу же за параметром.
Этот метод явным образом выбивается из модели шаблонов, так как
вместо информации, предоставляемой эталонным кодом, использует наши
ожидания о представлении списков, которые не всегда применимы,
несмотря на то, что для большинства реальных ситуаций данное форматирование
соответствует СК.
Достоинством подхода является простота его реализации.

\begin{figure}[h!]
  \begin{tabular}{p{\linewidth}}
    \centering
    \subfloat[Заполняющее форматирование списков]{
      \lstinputlisting[language = Java]{Podkopaev/codes/listEx1.java}
      \label{fig:listFill}
    }\\
    \centering
    \subfloat[Форматирование списка с переводом строки на каждый элемент]{
      \lstinputlisting[language = Java]{Podkopaev/codes/listEx2.java}
      \label{fig:listEveryLine}
    }
  \end{tabular}
  \caption{Пример форматирования списков в IDE}
\end{figure}

Другое решение заключается в использовании специального шаблона, который
задает переход между представлением головы списка и следующим обрабатываемым
элементом. По сути метод является сверткой списка, где начальным значением
является множество представлений первого элемента, а функция перехода с помощью
шаблона соединяет
посчитанные раскладки и результат форматирования следующего элемента.
Данный подход позволяет получить нестандартные способы форматирования
из эталонного кода (см. рис.~\ref{fig:listGoodLine}).

\begin{figure}[h!]
  \lstinputlisting[language = Java]{Podkopaev/codes/listEx3.java}
  \caption{Пример нестандартного форматирования списков}
  \label{fig:listGoodLine}
\end{figure}

На самом деле, одного шаблона перехода 
в большинстве ситуаций недостаточно,
так как получаемое представление списка может стать слишком широким и не попасть
в ограничение (в случае, если шаблон \emph{``горизонтальный''}).
Так, необходимо использовать согласованную группу шаблонов
(см. рис.~\ref{fig:tmpltGroup}), которая
позволит реализовывать некоторое обобщение заполняющего метода.
Недостатком такого способа решения является сложность в идентификации подобных
групп шаблонов, а также в сильно возрастающем числе самих шаблонов при наивном
использовании всех переходов из эталонного кода.

\begin{figure}[h!]
  \centering
  \subfloat[``Горизонтальный'' шаблон]{
    \makebox[0.4\textwidth]{
      \lstinputlisting[language = Java]{Podkopaev/codes/horListEx.java}
    }
  }
  ~
  \subfloat[``Вертикальный'' шаблон]{
    \makebox[0.4\textwidth]{
      \lstinputlisting[language = Java]{Podkopaev/codes/vertListEx.java}
    }
  }
  \caption{Группа шаблонов для списков}
  \label{fig:tmpltGroup}
\end{figure}

Кроме того, некоторые стили
форматирования списков могут быть сильно специфичными для мест использования.
В частности, форматирование списка реализуемых интерфейсов Java-класса может
концептуально зависеть от шаблона, используемого для форматирования всего класса
в целом. Эта специфика приводит к усложнению общего алгоритма в смысле реализации
и алгоритмически, так как для каждого узла дерева, переданного на печать,
надо хранить не только единый набор раскладок, но и оптимальные
множества представлений для каждого шаблона более высокого уровня.

% (см. пример на
% рисунке~\ref{fig:listClassicEx}).

% \begin{figure}[h!]
%   \textbf{Тут надо привести какой-нибудь пример}

%   \caption{Пример классической печати списков}
%   \label{fig:listClassicEx}
% \end{figure}

\subsubsection{Обработка комментариев.}

Отдельно стоит отменить задачу обработки комментариев. В целом, комментарии
существенно выбиваются из общей картины. Первой их особенностью является то,
что обычные неструктурированные комментарии, которые не
предназначены для автоматической обработки подобно
JavaDoc\footnote{\cd{http://java.sun.com/j2se/javadoc/}}
и Doxygen\footnote{\cd{http://doxygen.org/}},
невозможно видоизменить, так как для этого необходимо понимать семантику
комментария. Вторая особенность заключается в том, что для комментариев нет
специально отведенных мест в абстрактном синтаксическом дереве программы
(в соответствии с некоторыми определениями, комментариев в нем вообще быть не может),
а значит для подхода, ориентированного на структурное синтаксическое сравнение, они
являются специальным случаем.

В рамках данной работы было применен следующий подход: каждый блок комментариев
связывается с узлом синтаксического дерева. Для связывания выбирается узел, который
ближе всего к комментарию, при этом комментарий лежит полностью в его родительском узле.
После построения вариантов раскладки для выбранного узла, к каждому из них
присоединяется комментарий сверху или снизу, в зависимости от изначального положения.
Получившееся множество представлений считается ответом для выбранного узла.

Существенным недостатком того, что комментарии остаются без изменений,
является то, что нельзя управлять их шириной, что может привести к нежелательному
увеличению минимальной возможной ширины раскладки всего дерева.
Так, наличие строки комментария в
100 символов не дает возможности отформатировать текст на меньшую ширину.
В частности, это объясняет, почему в нижеследующем анализе производительности для
форматирования используются столь большие ширины (200 и 250). Возможным решением
этой проблемы может быть смягчение требования на ширину текста --- разрешение
комментариям выходить за границы.

Дополнительным артефактом приведенного алгоритма обработки комментариев является то,
что результат работы
принтер-плагина не является его неподвижной точкой, поскольку при повторном запуске
комментарии могут быть присоединены к другим синтаксическим узлам, нежели при предыдущем
запуске.

Также комментарии влияют на получение шаблонов:
наличие комментария внутри или рядом с синтаксической структурой
может серьезно менять форматирование в эталонном коде, поэтому от большинства
шаблонов, содержащих комментарии, приходится отказываться.

\subsubsection{Анализ производительности.}

Для оценки производительности были рассмотрены средние и большие исходные файлы
проекта IntelliJ IDEA Community
Edition\footnote{\cd{http://github.com/jetbrains/intellij-community/}}.
Средние файлы проекта имеют размер от 100-500 строк, большие --- несколько тысяч строк.
Результаты производительности для средних и больших файлов приведены в
таблице~\ref{tbl:pluginPerformanceTbl}.

\begin{table}[h!]
	\centering

  % \subfloat[Ширина 200] {
    % \centering
    \begin{tabular}{c|c|c| c}
    Имя файла & Число строк & Шир. 200 & Шир. 250 \\
    \hline
    SearchRequestCollector.java & 169 & 0.04 & 0.05\\
    XDebugProcess.java & 236 & 0.02 & 0.02\\
    InitialConfigurationDialog.java & 455 & 0.11 & 0.11 \\
    QuickEditHandler.java & 504 & 0.21 & 0.21\\
    PsiDirectoryImpl.java & 618 & 0.11 & 0.12\\
    \hline
    Messages.java & 2007 & 0.73 & 0.74 \\
    UIUtil.java & 2808 & 1.15 & 1.14 \\
    AbstractTreeUi.java & 5112 & 1.62 & 2.01 \\
    EditorImpl.java & 6789 & 2.07 & 2.09\\
    ConcurrentHashMap.java & 7191 & 1.38 & 1.39
    \end{tabular}
  % }
  \vskip 2mm
  \caption{Время форматирования файлов (в секундах)}
  \label{tbl:pluginPerformanceTbl}
\end{table}

Эти данные показывают, что принтер может быть использован для
форматирования малых и средних файлов, но на больших файлах время
работы слишком велико для практического применения. Проблему производительности
можно будет считать решенной, если время работы снизится до 0.5 секунд.

\subsubsection{Открытые проблемы.}

Проблемой, которую не получилось решить в рамках данной работы,
является задание порядка поддеревьев для конструкций, которые
его явным образом не определяют. К примеру, это верно для классов в Java:
часто порядок полей, методов и подклассов может быть произвольным в контексте
семантики программы, но в большинстве СК описаны рекомендации для их размещения
относительно друг друга. В форматтерах IDE данная проблема решается просто ---
среди настроек есть указание порядка подконструкций для подобных случаев.
В шаблонах это свойство явно не задается. Кроме попытки использования
уже существующего подхода, данную проблему также можно 
решать с помощью обучения на эталонном репозитории или с дополнительным
конфигурационным файлом. Но в целом такая задача несколько выбивается из
простой печати синтаксического дерева, так как изменение порядка, к примеру,
Java-полей может привести к изменению семантики программы, поэтому для проведения
упорядочивания элементов конструкций может требоваться дополнительный статический
анализ.

\section*{Заключение}

% \subsection*{Результаты}
% \addcontentsline{toc}{subsection}{Результаты}

В рамках данной работы достигнуты следующие результаты:
\begin{enumerate}
\item Для задачи поиска оптимальной раскладки документа,
определенного с помощью комбинаторов из~\cite{swierstra}, на заданную ширину
конструктивно доказана ее линейность относительно размеров дерева комбинаторов;
\item Разработан подход к заданию принтеров с помощью образцов для языков программирования;
\item Реализован плагин форматирования программных текстов на языке Java для IntelliJ IDEA
в рамках апробации общего подхода.
\end{enumerate}


% \subsection*{Дальнейшая работа}
% \addcontentsline{toc}{subsection}{Дальнейшая работа}

Существует несколько направлений для развития данной работы.
В рамках плагина стоит добавить
анализ эталонного репозитория на полноту, чтобы для полученного по
эталонному коду принтера можно было гарантировать возможность
обработки любого абстрактного синтаксического дерева Java.
Также для возможности практического применения необходимо повысить
производительность плагина.
Для общего подхода самой важной задачей является разработка
абстрагированной от целевого языка программной системы. Кроме того,
необходимо получить способ описания порядка поддеревьев для тех
случаев, когда он не задан явно синтаксисом языка.

\begin{thebibliography}{9001}

\bibitem{CoursePaper} А.Подкопаев. Форматирование текста программ на основе комбинаторов, сопоставления с образцом и синтаксических шаблонов
// Труды лаборатории языковых инструментов, 2013.

% \bibitem{haskellImpl} Реализация и тестовые примеры
% оптимальных принтер-комбинаторов на Haskell, \cd{http://github.com/anlun/polynomialPPCombinators}

\bibitem{burs} A.V.Aho, M.Ganapathi, S.W.K.Tjiang. Code Generation Using Tree Matching and Dynamic Programming // ACM Transactions on Programming Languages and Systems, 
11(4), 1989.


\bibitem{maintance} G.Alkhatib. The maintenance problem of application software:
an empirical analysis // Journal of Software Maintenance, 4(2):83–104, 1992.

\bibitem{swierstra} P.Azero, S.D.Swierstra. Optimal Pretty-Printing Combinators. \cd{http://www.cs.ruu.nl/groups/ST/Software/PP}, 1998.

\bibitem{swiComb} P.Azero, S.D.Swierstra, J.Saraiava. Designing and Implementing Combinator Languages // Advanced Functional Programming, 1999.

\bibitem{chitil} O.Chitil. Pretty Printing with Lazy Dequeues // ACM Trans. Program. Lang. Syst. 27(1), 2005.

\bibitem{tata} H.Comon, M.Dauchet, R.Gilleron \emph{et al}. Tree Automata Techniques and Applications, \cd{http://www.grappa.univ-lille3.fr/tata}, 2007.

\bibitem{learning} F.Corbo, C.Del Grosso, M.Di Penta. Smart Formatter: Learning Coding Style from
Existing Source Code // Software Maintenance. ICSM 2007. IEEE International Conference, pp.525,526, 2-5, 2007.

\bibitem{poset} C.Daskalakis, R.M.Karp, E.Mossel, S.Riesenfeld, E.Verbin.
Sorting and Selection in Posets.
In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA '09). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 392-401, 2009.

\bibitem{hughes} J.Hughes. The Design of a Pretty-printing Library // Advanced Functional Programming, 1995.

\bibitem{eclipse} S.Jackson, P.Devanbu, K.Ma. Stable, Flexible, Peephole Pretty-Printing // Journal Science of Computer Programming, 72(1-2), 2008.

\bibitem{jongeEveryOccasion} M.De Jonge. A Pretty-Printer for Every Occasion // Proceedings of the 2nd International Symposium on Constructing 
Software Engineering Tools, 2000.

\bibitem{jongeReengine} M.De Jonge. Pretty-printing for Software Reengineering // Proceedings of the International Conference On Software Maintenance, 2002.

\bibitem{kiselyov} O.Kiselyov, S.Peyton-Jones, A.Sabry. Lazy vs. Yield: Incremental, Linear Pretty-Printing // 10th Asian Symposium on Programming Languages and Systems, 
2012.

\bibitem{oppen} D.C.Oppen. Pretty-printing // ACM Transactions on Programming Languages and Systems, 2(4), 1980.

\bibitem{peytonJones} Peyton Jones S. Haskell Pretty-printer Library // \cd{http://www.haskell.org/ghc/docs/latest/html/libraries/
pretty-1.1.1.0/Text-PrettyPrint.html}, 1997.

\bibitem{podkopaevBoulytchev} A.Podkopaev, D.Boulytchev.
Polynomial-Time Optimal Pretty-Printing Combinators with Choice // Принято на PSI-2014. 

\bibitem{rendelInvert} T.Rendel, K.Ostermann. Invertible syntax descriptions: unifying parsing and pretty printing // SIGPLAN Not. 45, 11, 1-12, 2010.

\bibitem{codingStandarts} J.Shore. The Art of Agile Development. O'Relly Media, 2010.

\bibitem{swierstra04} S.D.Swierstra. Linear, Online, Functional Pretty Printing (corrected and extended version).
Technical report, UU-CS-2004-025a. Institute of Information and Computing Sciences, Utrecht University, 2004.

\bibitem{swierstraChitil} S.D.Swierstra, O. Chitil. Linear, Bounded, Functional Pretty-printing // J. Funct. Program., Vol. 19,
2009.

\bibitem{brandBox} M.Van den Brand, E.Visser. Generation of Formatters for Context-free Languages // ACM Trans. Softw. Eng. Methodol., 5(1), 1996.

\bibitem{wadler} P.Wadler. A Prettier Printer // The Fun of Programming. Palgrave MacMillan, 2003.


\end{thebibliography}

\section*{Программный код полиномиальной сложности оптимальных принтер-комбинаторов на языке Haskell}

\lstinputlisting[language=haskell]{Podkopaev/codes/PrettyLib.hs}
